<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(A卷,100分)- 查找重复代码（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>小明负责维护项目下的代码&#xff0c;需要查找出重复代码&#xff0c;用以支撑后续的代码优化&#xff0c;请你帮助小明找出重复的代码。<br /> 重复代码查找方法&#xff1a;以字符串形式给定两行代码&#xff08;字符串长度 1 &lt; length &lt;&#61; 100&#xff0c;由英文字母、数字和空格组成&#xff09;&#xff0c;找出两行代码中的最长公共子串。<br /> 注&#xff1a;如果不存在公共子串&#xff0c;返回空字符串</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>输入的参数text1, text2分别表示两行代码</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>输出任一最长公共子串</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">hello123world<br /> hello123abc4</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">hello123</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">private_void_method<br /> public_void_method</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">_void_method</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:85px;">输入</td><td style="width:413px;">hiworld<br /> hiweb</td></tr><tr><td style="width:85px;">输出</td><td style="width:413px;">hiw</td></tr><tr><td style="width:85px;">说明</td><td style="width:413px;">无</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题可以使用动态规划求解&#xff0c;下面解释下本题动态规划解题思路。</p> 
<p>动态规划&#xff0c;一般是将大问题分解为规模更小的相同的子问题&#xff0c;如果子问题依旧很难求解&#xff0c;则继续分解&#xff0c;直到规模小到子问题可以被轻松求解。</p> 
<p>比如上面求两个字符串的最长公共子串&#xff0c;如果两个字符串很长&#xff0c;那么我们将很难一下子发现最长公共子串&#xff0c;那么我们可以只看两个字符串的部分范围&#xff0c;比如字符串str1&#xff0c;只看0~i范围&#xff0c;字符串str2&#xff0c;只看0~j范围&#xff0c;然后求解str1的0~i范围和str2的0~j范围的最长公共子串&#xff0c;最简单就是str1的0~0范围&#xff0c;即空串&#xff0c;和任意str2范围的最长公共子串都是空串&#xff0c;接着我们可以慢慢扩大str1的范围。</p> 
<p>可能上面说的还比较抽象&#xff0c;我们可以用一个二维数组dp来描述上面逻辑。</p> 
<p>dp[i][j] 表示的是&#xff0c;str1的0~i范围  和  str2的0~j范围   的公共子串的长度</p> 
<p>初始时&#xff0c;我们可以得出如下二维矩阵</p> 
<p><img alt="" height="667" src="https://img-blog.csdnimg.cn/b16121845583479fa6da42c86f601cd3.png" width="721" /></p> 
<p> 即str1取0~0&#xff0c;即空串时&#xff0c;和任意str2范围的公共子串的长度都是0。</p> 
<p>同理&#xff0c;str2取0~0&#xff0c;即空串时&#xff0c;和任意str1范围的公共子串的长度都是0。</p> 
<p></p> 
<p>接下来&#xff0c; str1取0~1范围&#xff08;即h&#xff09;&#xff0c;和str2取0~1范围&#xff08;即h&#xff09;&#xff0c;的公共子串其实就是h&#xff0c;因此长度为1。如下图所示</p> 
<p><img alt="" height="669" src="https://img-blog.csdnimg.cn/eca89a143c59480295315db745de82b2.png" width="706" /></p> 
<p>但是上面公共子串长度求解&#xff0c;也可以看成是&#xff0c;str1扩大范围新增的h&#xff0c;和str2扩大范围新增的h相同&#xff0c;因此出现了公共子串&#xff0c;那么就相当于在str1未扩大范围前&#xff08;即空串时&#xff09;&#xff0c;和str2未扩大范围前&#xff08;即空串时&#xff09;&#xff0c;的公共子串长度的基础上&#43;1。</p> 
<p>即&#xff1a;dp[1][1] &#61; dp[0][0] &#43; 1</p> 
<p>进一步分析&#xff0c;其实可得出状态转移方程&#xff1a;</p> 
<p>if(str1[i] &#61;&#61;&#61; str2[j])  dp[i][j] &#61; dp[i-1][j-1] &#43; 1</p> 
<p></p> 
<p>再接下来&#xff0c; str1还是取0~1范围&#xff08;即h&#xff09;&#xff0c;和str2取0~2范围&#xff08;即he&#xff09;,</p> 
<p><img alt="" height="666" src="https://img-blog.csdnimg.cn/6a838900f75c4a278e593d92a7317189.png" width="702" /></p> 
<p>此时str1还是相当于新增h&#xff0c;而str2相当于新增e&#xff0c;新增部分不相同&#xff0c;所以此处没有增长前面基础上得到的公共子串的长度。</p> 
<p>那么此时相当于 if(str1[i] !&#61;&#61; str2[j])  dp[i][j] &#61; dp[i-1][j-1] &#43; 0&#xff0c;</p> 
<p>但是这种思路是错误的&#xff0c;因为当str1,str2新增范围字符不同时&#xff0c;意味着公共子串的中断&#xff0c;我们应该将此时的dp[i][j]置为0&#xff0c;这样才能防止dp[i&#43;1][j&#43;1]对应的字符相同时&#xff0c;继承前面的公共子串长度。</p> 
<p>请看下面错误例子</p> 
<p><img alt="" height="290" src="https://img-blog.csdnimg.cn/ce177039a79743febff5107bec07169e.png" width="395" /></p> 
<p> 正确例子应该是</p> 
<p><img alt="" height="296" src="https://img-blog.csdnimg.cn/d67e17a8bd9f4abcad08523895fa0f4e.png" width="346" /></p> 
<p>因此正确的动态规划状态转移方程是&#xff1a;</p> 
<ul><li>dp[i][0] &#61; 0</li><li>dp[0][j] &#61; 0</li><li>if(str1[i] &#61;&#61;&#61; str2[j])  <span style="color:#fe2c24;">dp[i][j] &#61; dp[i-1][j-1] &#43; 1</span>   else dp[i][j] &#61; <span style="color:#fe2c24;">0</span></li></ul> 
<p></p> 
<p>但是此题并不是让我们求解最长的公共子串的长度&#xff0c;而是求出任一最长公共子串。因此我们可以在遍历求解上面二维矩阵每一个元素时&#xff0c;记录下公共子串最大的长度值&#xff0c;比如下面例子中&#xff0c;求解到黄色元素dp[2][2]时&#xff0c;得到了目前最大的公共子串长度2&#xff0c;</p> 
<p><img alt="" height="282" src="https://img-blog.csdnimg.cn/47a5e9b9096641009dec8a61b0658d6c.png" width="326" /></p> 
<p>因此我们可以从任一维度来获取这个公共子串&#xff0c;比如从列维度&#xff0c;相当于 str2.slice( j - maxLen, j)&#xff0c;其中j对应dp[i][j]中的j。maxLen&#61;dp[i][j]。</p> 
<p> <img alt="" height="278" src="https://img-blog.csdnimg.cn/1ec813e811b348babe5b9bdd75af2f96.png" width="318" /></p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 2) {
    const str1 &#61; lines[0];
    const str2 &#61; lines[1];
    console.log(getResult(str1, str2));
    lines.length &#61; 0;
  }
});

function getResult(str1, str2) {
  const n &#61; str1.length;
  const m &#61; str2.length;

  const dp &#61; new Array(n &#43; 1).fill(0).map(() &#61;&gt; new Array(m &#43; 1).fill(0));

  let max &#61; 0;
  let ans &#61; &#34;&#34;;

  for (let i &#61; 1; i &lt;&#61; n; i&#43;&#43;) {
    for (let j &#61; 1; j &lt;&#61; m; j&#43;&#43;) {
      if (str1[i - 1] &#61;&#61;&#61; str2[j - 1]) {
        dp[i][j] &#61; dp[i - 1][j - 1] &#43; 1;

        if (dp[i][j] &gt; max) {
          max &#61; dp[i][j];
          ans &#61; str1.slice(i - max, i);
        }
      } else {
        dp[i][j] &#61; 0;
      }
    }
  }

  return ans;
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    String str1 &#61; sc.nextLine();
    String str2 &#61; sc.nextLine();

    System.out.println(getResult(str1, str2));
  }

  public static String getResult(String str1, String str2) {
    int n &#61; str1.length();
    int m &#61; str2.length();

    int[][] dp &#61; new int[n &#43; 1][m &#43; 1];

    int max &#61; 0;
    String ans &#61; &#34;&#34;;

    for (int i &#61; 1; i &lt;&#61; n; i&#43;&#43;) {
      for (int j &#61; 1; j &lt;&#61; m; j&#43;&#43;) {
        if (str1.charAt(i - 1) &#61;&#61; str2.charAt(j - 1)) {
          dp[i][j] &#61; dp[i - 1][j - 1] &#43; 1;

          if (dp[i][j] &gt; max) {
            max &#61; dp[i][j];
            ans &#61; str1.substring(i - max, i);
          }
        } else {
          dp[i][j] &#61; 0;
        }
      }
    }

    return ans;
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
str1 &#61; input()
str2 &#61; input()


# 算法入口
def getResult(str1, str2):
    n &#61; len(str1)
    m &#61; len(str2)

    dp &#61; [[0 for i in range(m &#43; 1)] for j in range(n &#43; 1)]

    maxV &#61; 0
    ans &#61; &#34;&#34;

    for i in range(1, n &#43; 1):
        for j in range(1, m &#43; 1):
            if str1[i - 1] &#61;&#61; str2[j - 1]:
                dp[i][j] &#61; dp[i - 1][j - 1] &#43; 1

                if dp[i][j] &gt; maxV:
                    maxV &#61; dp[i][j]
                    ans &#61; str1[(i - maxV):i]
            else:
                dp[i][j] &#61; 0

    return ans


# 算法调用
print(getResult(str1, str2))
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>